from sys import stdin,stdout
from math import *
def read_list_line(elem_func=int):
return [elem_func(x) for x in stdin.readline().strip().split()]
def read_line(elem_func=str):
return elem_func(stdin.readline().strip())
def print_list_line(the_list,elem_func=str,sep=' ',end=""):
st=(sep.join([elem_func(x) for x in the_list]))+end
stdout.write(st)
return st
def print_line(st):
stdout.write(str(st)+"\n")
return st
maxa=31625
is_prime=[True]*(maxa)
primes=[]
is_prime[0]=False
is_prime[1]=False
for i in range(2,maxa):
if (is_prime[i]==True):
j=i
while ((i*j)<maxa):
is_prime[(i*j)]=False
j += 1
primes.append(i)
ntest=read_line(int)
def main():
global is_prime, primes, maxa
n = read_line(int)
a = read_list_line(int)
a.sort()
p_set=set()
for i in range(n):
x = a[i]
for p in primes:
if a[i] % p == 0:
if p in p_set:
print("YES")
return 0
p_set.add(p)
while (x % p == 0):
x = x // p
if x > 1:
if x in p_set:
print("YES")
return 0
p_set.add(x)
print("NO")
return 0
for test_case in range(1,1+ntest):
main()/*
* Author: UnPolinomio
* Time: 2023-01-30 02:18:51
**/
#include <bits/stdc++.h>
using namespace std;
#define _ \
ios_base::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0)
#define deb(x) cout << #x << ": " << (x) << '\n';
#define all(x) begin(x), end(x)
#define fore(x, a, b) for(lli x = a, ___lim___=b; x < ___lim___; ++x)
using lli = long long int;
using vi = vector<lli>;
using vb = vector<bool>;
using ii = pair<lli, lli>;
vi primes(lli n) {
vb p(n + 1, true);
for(lli i{2}; i * i <= n; ++i) {
if(!p[i]) continue;
for(lli j{i * i}; j <= n; j += i) p[j] = false;
}
vi ans{};
fore(i, 2, n + 1) if(p[i]) ans.push_back(i);
return ans;
}
bool solve(vi& a) {
static vi ps{ primes(ceil(sqrt(1000000000)))};
unordered_set<lli> s{};
for(auto &el : a) {
for(auto p : ps) {
if(el % p == 0) {
if(s.count(p)) return true;
while(el % p == 0) el /= p;
s.insert(p);
}
}
}
for(auto &el : a) {
if(el == 1) continue;
if(s.count(el)) return true;
s.insert(el);
}
return false;
}
int main() {
_;
lli t{}, n{};
cin >> t;
while(t--) {
cin >> n;
vi a(n);
for(auto &el : a) cin >> el;
cout << (solve(a) ? "YES" : "NO") << '\n';
}
return EXIT_SUCCESS;
}
1711B - Party | 1702D - Not a Cheap String |
1714F - Build a Tree and That Is It | 1703F - Yet Another Problem About Pairs Satisfying an Inequality |
610A - Pasha and Stick | 1200A - Hotelier |
1091A - New Year and the Christmas Ornament | 1352B - Same Parity Summands |
1102A - Integer Sequence Dividing | 630B - Moore's Law |
1004A - Sonya and Hotels | 1680B - Robots |
1690A - Print a Pedestal (Codeforces logo) | 1295A - Display The Number |
1077A - Frog Jumping | 1714G - Path Prefixes |
1369C - RationalLee | 289B - Polo the Penguin and Matrix |
1716A - 2-3 Moves | 1670B - Dorms War |
1716B - Permutation Chain | 987A - Infinity Gauntlet |
1676G - White-Black Balanced Subtrees | 1716D - Chip Move |
1352F - Binary String Reconstruction | 1487B - Cat Cycle |
1679C - Rooks Defenders | 56A - Bar |
1694B - Paranoid String | 35A - Shell Game |